With ever increasing usage of the Internet for transmitting messages comes an increasing need to secure such communications. The most obvious way to secure Internet traffic is to encrypt it. However, the protocol for transmitting messages over the Internet (i.e., the Internet Protocol or IP) is packet based. That is, a message to be transmitted is divided into sections or packets and transmitted separately so that different packets may take different routes to arrive at the intended destination, based on the availability of a route. This allows for more reliable and efficient transmission since a dedicated line need not be established between the sender and receiver for the entire duration of the transmission and the loss of a route does not halt the transmission of the packets. The packets will be sent over the route that is available at the time. However, the packets may not arrive at the intended destination in the order that they appear in the message. Therefore, information must be added to each packet to indicate how the packets are to be reconstructed by the receiver to recover the intended message. This added information is often referred to as header information or information added to the header of a packet.
Sending messages in packet form is efficient from a transmission standpoint but causes problems from a security standpoint. If the encryption method used to encrypt packets requires the packets to be decrypted in the order they appear in the message then decryption cannot start until all packets are received. Since many messages are transmitted at the same time over the Internet by interspersing the packets of various messages, a bottleneck of packets awaiting decryption may accumulate at a receiver until all of the packets of a particular message arrive. This is undesirable from a network performance standpoint. Therefore, there is a need for a IP encryption method that allows for the decryption of an encrypted packet as soon as it is received by a receiver. Since users of the Internet value increased performance, an encryption method that allows for efficient encryption and decryption is highly desired. Pipelining is a method of attaining efficiency. It makes use of the fact that most block encryption algorithms are composed of one function repeated numerous times to encrypt a block of plaintext. Pipelining is achieved by replicating the function employed, in hardware or in software, as many times as it is repeated to achieve the result. This allows successive blocks of plaintext to be processed as soon as the first block has finished the first step in the pipelined process. Anytime a block moves to another process in the pipeline, a new block may be processed. The efficiency of a non-pipelined block cipher that takes n steps can be improved n times by pipelining it. Therefore, a pipelined method of encrypting and decrypting Internet Protocol transmission is needed.
The Encapsulating Security Payload (ESP) is a protocol for providing encryption and authentication of data packets transmitted over the Internet. ESP uses a hash algorithm to provide authentication. Hash algorithms cannot be pipelined. Therefore, ESP is not as efficient as a pipelined algorithm.
A cryptographic algorithm, such as a codebook, may be used in various cryptographic modes by configuring the algorithm with different types of feedback and incorporating different types of logic functions. Three well known modes for cryptographic codebooks are Electronic Codebook Mode (ECB), Cipher Block Chaining Mode (CBC), and Counter Mode (CM).
ECB may be pipelined. However, by repeating plaintext blocks (i.e., repeating parts of a message in its unscrambled form), ECB will repeat blocks of ciphertext (i.e., parts of a scrambled message will repeat). Such repeats give unintended recipients information about the encryption process that could help them acquire the plaintext message. It is preferred that a cryptographic algorithm not provide such information.
In CM, a counter (typically a one-up counter, but other counts are possible) provides input to the cryptographic codebook. The output along with plaintext is processed by an exclusive-or function to produce ciphertext. CM may be pipelined. However, changing bits in CM ciphertext produces predictable changes to CM plaintext, another characteristic to be avoided.
CBC doesn't have the characteristic that a repeat of a plaintext block produces a repeat of a ciphertext block. However, CBC cannot be pipelined because the encryption of a next plaintext block cannot start until the encryption of a previous plaintext block is completed. Therefore, CBC is not as efficient as a pipelined method.
The National Institute of Standards and Technology (NIST), an agency of the U.S. Department of Commerce's Technology Administration, announced the approval of the Federal Information Processing Standard (FIPS) for the Advanced Encryption Standard (AES) as described in FIPS Publication 197 (FIPS PUB 197), which is hereby incorporated by reference into the present specification. This standard specifies a symmetric encryption algorithm that may be used by U.S. Government organizations to protect sensitive, but unclassified, information. The AES was designed to replace the Data Encryption Standard (DES). However, Triple DES remains an approved algorithm for U.S. Government use for the foreseeable future. Single DES is being phased out and is currently permitted only in legacy systems. DES and Triple DES are described in FIPS PUB 46-3, which is incorporated by reference into the specification of the present invention.
An article by Charanjit S. Jutla entitled “Encryption Modes with Almost Free Message Integrity,” published on Dec. 8, 2000, discloses a method of operation for block encryption which provides confidentiality of data and message integrity. The present invention does not use the method disclosed in this article.
U.S. Pat. No. 4,910,777, entitled “PACKET SWITCHING ARCHITECTURE PROVIDING ENCRYPTION ACROSS PACKETS,” discloses a device for and method of encrypting a flag in each packet, and leaving the rest of the packet unencrypted, before transmission and transmitting special packets to achieve syncronization with the decryptor. The present invention does not encrypt a flag, leave the rest of a packet unencrypted, and transmit special packets to achieve synchronization. U.S. Pat. No. 4,910,777 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,594,869, entitled “METHOD AND APPARATUS FOR END-TO-END ENCRYPTION OF A DATA PACKET IN A COMPUTER NETWORK,” discloses a device for and method of encrypting packets for a specific network protocol using programmable registers for identifying the specific protocol, whether or not decryption should be performed, and the starting location for decryption. The present invention does not use such programmable registers. U.S. Pat. No. 5,594,869 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,684,876, entitled “APPARATUS AND METHOD FOR CIPHER STEALING WHEN ENCRYPTING MPEG TRANSPORT PACKETS,” discloses a device for and method of encrypting packets, where each packet is parsed into a first part, a second part, and a residual part. The second part and the residual part are encrypted using a block cipher to form a first encrypted block. The first encrypted block is parsed into a third part and a fourth part. The first part and the third part are encrypted to form a second encryption block. The present invention does not use such an encryption scheme. U.S. Pat. No. 5,684,876 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,898,784, entitled “TRANSFERRING ENCRYPTED PACKETS OVER A PUBLIC NETWORK,” discloses a method of passing encrypted network packets to a computer on an internal network, examining a field in each network packet to determine which encryption algorithm was used to encrypt the network packet, determining which virtual tunnel each network packet was sent over and routing the same in accordance with its virtual tunnel, and encrypting network packets for transmission over internal and public networks connected to a network interface computer. The present invention does not use such a method. U.S. Pat. No. 5,898,784 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,052,466, entitled “ENCRYPTION OF DATA PACKETS USING A SEQUENCE OF PRIVATE KEYS GENERATED FROM A PUBLIC KEY EXCHANGE,” discloses a device for and method of partitioning a cipher stream into a sequence of secondary keys. The secondary keys are then used to encrypt packets either one key per packet or one key for all the packets. An index of the keys are sent to the receiver so that it knows what keys to use to decrypt the encrypted packets. The present invention does not use such a method. U.S. Pat. No. 6,052,466 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,170,057, entitled “MOBILE COMPUTER AND METHOD OF PACKET ENCRYPTION AND AUTHENTICATION IN MOBILE COMPUTING BASED ON SECURITY POLICY OF VISITED NETWORK,” discloses a device for and method of controlling the activation of packet encryption and authentication. The present invention does not use such a method. U.S. Pat. No. 6,170,057 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,185,680, entitled “PACKET AUTHENTICATION AND PACKET ENCRYPTION/DECRYPTION SCHEME FOR SECURITY GATEWAY,” discloses a device for and method of packet authentication, encryption, and decryption using link-by-link authentication and determining whether or not to encrypt or decrypt a packet based on information on a computer, encryption information, signature information, or information in the packet. The present invention does not use such a method. U.S. Pat. No. 6,185,680 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,219,791, entitled “METHOD AND APPARATUS FOR GENERATING AND VERIFYING ENCRYPTED DATA PACKETS,” discloses a device for and method of embedding error detection codes in the encrypted packets and checking the same to prevent the transmission of erroneously encrypted packets. The present invention does not use such a method. U.S. Pat. No. 6,219,791 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. Appl. No. US 2002/0002675 A1, entitled “SECURE ENCRYPTION OF DATA PACKETS FOR TRANSMISSION OVER UNSECURED NETWORKS,” discloses a device for and method of using pure random numbers from a one-time pad to encrypt and order encrypted bytes of a packet. The present invention does not use such a method. U.S. Pat. Appl. No. US 2002/0002675 A1 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. Appl. No. US 2002/0023209 A1, entitled “ENCRYPTION AND DECRYPTION OF DIGITAL MESSAGES IN PACKET TRANSMITTING NETWORKS,” discloses a device for and method of encrypting packets of varying lengths using an encryption algorithm that varies depending on the plaintext to be encrypted. The present invention does not use such a method. U.S. Pat. Appl. No. US 2002/0023209 A1 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. Appl. No. US 2002/0129243 A1, entitled “SYSTEM FOR SELECTIVE ENCRYPTION OF DATA PACKETS,” discloses a device for and method of encrypting only certain of the packets and leaving the rest unencrypted. The present invention does not use such a method. U.S. Pat. Appl. No. US 2002/0129243 A1 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. Appl. No. US 2003/0131233 A1, entitled “EFFICIENT PACKET ENCRYPTION METHOD,” discloses a method of encrypting packets using an S-vector, the sequence numbers, and two other variables to encrypt successive packets. The present invention does not use such a method. U.S. Pat. Appl. No. US 2003/0131233 A1 is hereby incorporated by reference into the specification of the present invention.